#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 利用递归函数计算阶乘
# N! = 1 * 2 * 3 * ... * N
def fact(n):
    if n == 1:
        return 1
    return n * fact(n-1)


# print('fact(1) =', fact(1))
# print('fact(5) =', fact(5))
# print('fact(10) =', fact(10))


# 利用递归函数移动汉诺塔:
# 有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按大小顺序叠放着n个不同大小的圆盘(上面小，小面大),
# 要把所有盘子一个一个移动到柱子C上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方
'''
认识汉诺塔的目标：把A柱子上的N个盘子移动到C柱子
递归的思想就是把这个目标分解成三个子目标
子目标1：将前n-1个盘子从a移动到b上
子目标2：将最底下的最后一个盘子从a移动到c上
子目标3：将b上的n-1个盘子移动到c上
然后每个子目标又是一次独立的汉诺塔游戏，也就可以继续分解目标直到N为1 
'''
def move(n, a, b, c):
	if n ==1 :
		x=a.pop(0)
		c.insert(0, x)
	else:
		move(n-1, a, c, b)
		move(1, a, b, c)
		move(n-1, b, a, c)


# print("before move, a={0}, b={1}, c={2}".format(a, b, c))
# print("after move, a={0}, b={1}, c={2}".format(a, b, c))
# id(对象) 查看对象的内存地址
# print("a'id: {0}, b'id: {1}, c'id: {2}".format(id(a), id(b), id(c)))

a=[1]
b=[]
c=[]
move(1, a, b, c)

print("")

a=[1,2]
b=[]
c=[]
move(2, a, b, c)

print("")

a=[1,2,3]
b=[]
c=[]
move(3, a, b, c)

print("")
a=[1,2]
b=['b']
c=['c']
move(2, a, b, c)


